package com.anodyzed.onyx.util;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Implements the {@link java.util.Map} contract using a top-down splay tree.
 * The map is sorted according to the {@linkplain Comparable natural
 * ordering} of its keys, or by a {@link Comparator} provided at map
 * creation time, depending on which constructor is used.
 *
 * <p>Note that the ordering maintained by a sorted map (whether or not an
 * explicit comparator is provided) must be <i>consistent with equals</i> if
 * this sorted map is to correctly implement the <tt>Map</tt> interface.  (See
 * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
 * <i>consistent with equals</i>.)  This is so because the <tt>Map</tt>
 * interface is defined in terms of the equals operation, but a map performs
 * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
 * method, so two keys that are deemed equal by this method are, from the
 * standpoint of the sorted map, equal.  The behavior of a sorted map
 * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
 * just fails to obey the general contract of the <tt>Map</tt> interface.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a map concurrently, and at least one of the
 * threads modifies the map structurally, it <i>must</i> be synchronized
 * externally. (Due to the self-optimizing nature of a Splay Tree, even
 * <tt>get</tt>ting a value from the map during iteration will cause a
 * structural modification.)  This is  typically accomplished by synchronizing 
 * on some object that naturally encapsulates the map. If no such object 
 * exists, the map should be "wrapped" using the
 * {@link java.util.Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the map: <pre>
 *   SortedMap m = Collections.synchronizedSortedMap(new SplayTreeMap(...));</pre>
 *
 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
 * returned by all of this class's "collection view methods" are
 * <i>fail-fast</i>: if the map is structurally modified at any time after the
 * iterator is created, in any way except through the iterator's own
 * <tt>remove</tt> method, the iterator will throw a {@link
 * java.util.ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>java.util.ConcurrentModificationException</tt> on a best-effort 
 * basis. Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
 * and its views represent snapshots of mappings at the time they were
 * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
 * method. (Note however that it is possible to change mappings in the
 * associated map using <tt>put</tt>.)
 *
 * Based on code available at http://www.link.cs.cmu.edu/splay/
 * This code is in the public domain. 
 *  
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Chris Pratt and Danny Sleator <sleator@cs.cmu.edu>
 * @version 2011/12/15
 * @see java.util.Map
 * @see java.util.TreeMap
 * @see java.lang.Comparable
 * @see java.util.Comparator
 * @see java.util.Collection
 */
@SuppressWarnings("serial")
public class SplayTreeMap<K,V> extends AbstractMap<K,V> implements Serializable {

  static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;                   // The data in the node
    V value;                 // The data Payload
    Entry<K,V> parent;       // Parent
    Entry<K,V> left;         // Left child
    Entry<K,V> right;        // Right child

    Entry (K key,V value,Entry<K,V> parent) {
      this.key = key;
      this.value = value;
      this.parent = parent;
      left = right = null;
    } //Entry

    /**
     * Returns the key.
     *
     * @return the key
     */
    @Override
    public K getKey () {
      return key;
    } //getKey

    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    @Override
    public V getValue () {
      return value;
    } //getValue

    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    @Override
    public V setValue (V value) {
      V oldValue = this.value;
      this.value = value;
      return oldValue;
    } //setValue

    @Override
    public boolean equals (Object o) {
      if(!(o instanceof Map.Entry)) {
        return false;
      }
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;
      return Misc.equals(key,e.getKey()) && Misc.equals(value,e.getValue());
    } //equals

    @Override
    public int hashCode () {
      int keyHash = ((key == null) ? 0 : key.hashCode());
      int valHash = ((value == null) ? 0 : value.hashCode());
      return keyHash ^ valHash;
    } //hashCode

    @Override
    public String toString () {
      return key + "=" + value;
    } //toString

  } //Entry

  private final Entry<K,V> header = new Entry<K,V>(null,null,null); // For splay
  private transient Entry<K,V> root;

  private final Comparator<? super K> comparator,assignedComparator;

  private transient int size;

  private Set<Map.Entry<K,V>> entrySet = null;

  /**
   * The number of structural modifications to the tree.
   */
  private transient int modCount = 0;

  public SplayTreeMap () {
    this.root = null;
    this.size = 0;
    this.comparator = new Comparator<K>() {
      /**
       * Perform a Natural Order Comparison
       */
      @Override
      @SuppressWarnings("unchecked")
      public int compare (K k1,K k2) {
        return ((Comparable<? super K>)k1).compareTo(k2);
      } //compare
    };
    this.assignedComparator = null;
  } //SplayTreeMap

  /**
   * Constructor
   *
   * @param comparator The Comparator used to order the tree
   */
  public SplayTreeMap (Comparator<? super K> comparator) {
    this.root = null;
    this.size = 0;
    this.comparator = this.assignedComparator = comparator;
  } //SplayTreeMap

  /**
   * Return the Comparator assigned during the construction of this Splay Tree Map
   *
   * @return Assigned Comparator 
   */
  public Comparator<? super K> comparator () {
    return assignedComparator;
  } //comparator

  /**
   * Return the Set of Map Entries
   *
   * @return Set of Map Entries
   */
  @Override
  public Set<Map.Entry<K,V>> entrySet () {
    if(entrySet == null) {
      entrySet = new EntrySet();
    }
    return entrySet;
  } //entrySet

  /**
   * Find an item in the tree. 
   *  
   * @param key The entry key 
   * @return The matching entry
   */
  public Entry<K,V> find (K key) {
    if(root != null) {
      splay(key);
      return (comparator.compare(root.key,key) == 0) ? root : null;
    }
    return null;
  } //find

  /**
   * Get the Value associated with the specified Key
   *
   * @param key The Entry Key
   * @return The Entry Value
   */
  @Override
  @SuppressWarnings("unchecked")
  public V get (Object key) {
    Entry<K,V> entry = find((K)key);
    return (entry != null) ? entry.value : null;
  } //get

  /**
   * Associate the supplied value with the provided key
   *
   * @param key The Entry Key 
   * @param value The Entry Value 
   * @return The replaced Entry Value (or null)
   */
  @Override
  public V put (K key,V value) {
    if(root == null) {
      root = new Entry<K,V>(key,value,null);
      ++modCount;
      ++size;
    } else {
      int c;
      splay(key);
      if((c = comparator.compare(key,root.key)) != 0) {
        Entry<K,V> n = new Entry<K,V>(key,value,root);
        if(c < 0) {
          n.left = root.left;
          n.right = root;
          root.left = null;
        } else {
          n.right = root.right;
          n.left = root;
          root.right = null;
        }
        root = n;
        ++size;
      } else {
        V ret = root.value;
        root.value = value;
        return ret;
      }
    }
    return null;
  } //put

  /**
   * Check whether the Map contains the supplied Key
   *
   * @param key The Entry Key
   * @return {@code true} if an entry == {@code key} exists in the map
   */
  @Override
  @SuppressWarnings("unchecked")
  public boolean containsKey (Object key) {
    return find((K)key) != null;
  } //containsKey

  /**
   * Return the number of entries in the map
   *
   * @return Map entry count
   */
  @Override
  public int size () {
    return size;
  } //size

  /**
   * Test if the tree is logically empty. 
   *  
   * @return true if empty, false otherwise.
   */
  @Override
  public boolean isEmpty () {
    return root == null;
  } //isEmpty

  /**
   * Clear all the entries from the Map
   */
  @Override
  public void clear () {
    modCount++;
    size = 0;
    root = null;
  } //clear

  /**
   * Remove from the tree. 
   *  
   * @param key the item to remove.
   */
  @Override
  @SuppressWarnings("unchecked")
  public V remove (Object key) {
    splay((K)key);
    if(comparator.compare((K)key,root.key) == 0) {
        // Now delete the root
      if(root.left == null) {
        root = root.right;
      } else {
        Entry<K,V> x = root.right;
        root = root.left;
        splay((K)key);
        root.right = x;
        setParent(x,root);
      }
      setParent(root,null);
    }
    return null;
  } //remove

  /**
   * Find the leftmost Entry (the smallest key)
   *
   * @return The Leftmost entry
   */
  private Entry<K,V> leftmost () {
    Entry<K,V> entry = root;
    if(root != null) {
      while(entry.left != null) {
        entry = entry.left;
      }
    }
    return entry;
  } //leftmost

  /**
   * Find the smallest key in the tree.
   *
   * @return the First Map Key
   */
  public K firstKey () {
    Entry<K,V> min = leftmost();
    if(min != null) {
      splay(min.key);
      return min.key;
    }
    throw new NoSuchElementException();
  } //findMin

  /**
   * Find the rightmost Entry (the largest key)
   *
   * @return The Rightmost entry
   */
  public Entry<K,V> rightmost () {
    Entry<K,V> entry = root;
    if(root != null) {
      while(entry.right != null) {
        entry = entry.right;
      }
    }
    return entry;
  } //rightmost

  /**
   * Find the largest key in the tree.
   *
   * @return The Last Map Key
   */
  public K lastKey () {
    Entry<K,V> max = rightmost();
    if(max != null) {
      splay(max.key);
      return max.key;
    }
    throw new NoSuchElementException();
  } //findMax

  /**
   * Returns the successor of the specified Entry, or null if no such.
   *
   * @param t The entry before the requested entry
   * @return The entry after the specified entry
   */
  static <K,V> Entry<K,V> successor (Entry<K,V> t) {
    if(t != null) {
      Entry<K,V> p;
      if(t.right != null) {
        p = t.right;
        while(p.left != null) {
          p = p.left;
        }
      } else {
        p = t.parent;
        Entry<K,V> ch = t;
        while((p != null) && (ch == p.right)) {
          ch = p;
          p = p.parent;
        }
      }
      return p;
    }
    return null;
  } //successor

  /**
   * Returns the predecessor of the specified Entry, or null if no such.
   *
   * @param t The entry after the requested entry
   * @return The entry before the specified entry
   */
  static <K,V> Entry<K,V> predecessor (Entry<K,V> t) {
    if(t != null) {
      Entry<K,V> p;
      if(t.left != null) {
        p = t.left;
        while(p.right != null) {
          p = p.right;
        }
      } else {
        p = t.parent;
        Entry<K,V> ch = t;
        while((p != null) && (ch == p.left)) {
          ch = p;
          p = p.parent;
        }
      }
      return p;
    }
    return null;
  } //predecessor

  /**
   * Utility function to safely set the parent
   *
   * @param child The proposed Child 
   * @param parent The possible Parent
   */
  private static <K,V> void setParent (Entry<K,V> child,Entry<K,V> parent) {
    if(child != null) {
      child.parent = parent;
    }
  } //setParent

  /**
   * Internal method to perform a top-down splay.
   * 
   * splay(key) does the splay operation on the given key. If key is in the 
   * tree, then the Entry containing that key becomes the root.  If key is not
   * in the tree, then after the splay, key.root is either the greatest key < 
   * key in the tree, or the least key > key in the tree. 
   *
   * This means, among other things, that if you splay with a key that's larger 
   * than any in the tree, the rightmost node of the tree becomes the root. This 
   * property is used in the delete() method.
   *
   * @param key The Key to Splay on
   */
  private void splay (K key) {
    int c;
    if((c = comparator.compare(key,root.key)) != 0) {
      Entry<K,V> l, r, t, y;
      l = r = header;
      t = root;
      header.left = header.right = null;
      do {
        if(c < 0) {
          if(t.left == null) {
            break;
          }
          if(comparator.compare(key,t.left.key) < 0) {
            y = t.left;                            /* rotate right */
            t.left = y.right;
            setParent(y.right,t);
            y.right = t;
            setParent(t,y);
            t = y;
            if(t.left == null) {
              break;
            }
          }
          r.left = t;                              /* link right */
          setParent(t,r);
          r = t;
          t = t.left;
        } else {
          if(t.right == null) {
            break;
          }
          if(comparator.compare(key,t.right.key) > 0) {
            y = t.right;                           /* rotate left */
            t.right = y.left;
            setParent(y.left,t);
            y.left = t;
            setParent(t,y);
            t = y;
            if(t.right == null) {
              break;
            }
          }
          l.right = t;                             /* link left */
          setParent(t,l);
          l = t;
          t = t.right;
        }
      } while((c = comparator.compare(key,t.key)) != 0);
      l.right = t.left;                            /* assemble */
      setParent(t.left,l);
      r.left = t.right;
      setParent(t.right,r);
      t.left = header.right;
      setParent(header.right,t);
      t.right = header.left;
      setParent(header.left,t);
      root = t;
      root.parent = null;
      ++modCount;
    }
  } //splay

  abstract class AbstractEntryIterator<T> implements Iterator<T> {
    Entry<K,V> next;
    Entry<K,V> lastReturned;
    int expectedModCount;

    AbstractEntryIterator (Entry<K,V> first) {
      expectedModCount = modCount;
      lastReturned = null;
      next = first;
    } //AbstractEntryIterator

    @Override
    public final boolean hasNext () {
      return next != null;
    } //hasNext

	  final Entry<K,V> nextEntry () {
      Entry<K,V> e = next;
      if(e != null) {
        if(modCount == expectedModCount) {
          next = successor(e);
          lastReturned = e;
          return e;
        }
        throw new ConcurrentModificationException();
      }
      throw new NoSuchElementException();
    } //nextEntry

    final Entry<K,V> prevEntry () {
      Entry<K,V> e = next;
      if(e != null) {
        if(modCount == expectedModCount) {
          next = predecessor(e);
          lastReturned = e;
          return e;
        }
        throw new ConcurrentModificationException();
      }
      throw new NoSuchElementException();
    } //prevEntry

    @Override
    public void remove () {
      if(lastReturned != null) {
        if(modCount == expectedModCount) {
            // deleted entries are replaced by their successors
          if((lastReturned.left != null) && (lastReturned.right != null)) {
            next = lastReturned;
          }
          SplayTreeMap.this.remove(lastReturned.key);
          expectedModCount = modCount;
          lastReturned = null;
          return;
        }
        throw new ConcurrentModificationException();
      }
      throw new IllegalStateException();
    } //remove

  } //*AbstractEntryIterator

  final class EntryIterator extends AbstractEntryIterator<Map.Entry<K,V>> {
    EntryIterator (Entry<K,V> first) {
      super(first);
    } //EntryIterator

    @Override
    public Map.Entry<K,V> next () {
      return nextEntry();
    } //next
  } //*EntryIterator

//  final class ValueIterator extends AbstractEntryIterator<V> {
//    ValueIterator (Entry<K,V> first) {
//      super(first);
//    } //ValueIterator
//
//    @Override
//    public V next () {
//      return nextEntry().value;
//    } //next
//  } //*ValueIterator
//
//  final class KeyIterator extends AbstractEntryIterator<K> {
//    KeyIterator (Entry<K,V> first) {
//      super(first);
//    } //KeyIterator
//
//    @Override
//    public K next () {
//      return nextEntry().key;
//    } //next
//  } //*KeyIterator
//
//  final class DescendingKeyIterator extends AbstractEntryIterator<K> {
//    DescendingKeyIterator (Entry<K,V> first) {
//      super(first);
//    } //DescendingKeyIterator
//
//    @Override
//    public K next () {
//      return prevEntry().key;
//    } //next
//  } //*DescendingKeyIterator

  /**
   * EntrySet
   */
  final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    /**
     * Iterate over the Map Entries
     *
     * @return Map Entry Iterator
     */
    @Override
    public Iterator<Map.Entry<K,V>> iterator () {
      return new EntryIterator(leftmost());
    } //iterator

    /**
     * Get the matching Entry from the map
     *
     * @param entry The Map Entry to find
     * @return The matching entry, or null
     */
    private Entry<K,V> getEntry (Map.Entry<K,V> entry) {
      Entry<K,V> e = find(entry.getKey());
      return (e != null) ? (Misc.equals(e.getValue(),entry.getValue()) ? e : null) : null;
    } //getEntry

    /**
     * Check whether the Entry Set contains a matching Entry
     *
     * @param o The Map Entry to test
     * @return true if a matching Map Entry exists
     */
    @Override
    @SuppressWarnings("unchecked")
    public boolean contains (Object o) {
      return (o instanceof Map.Entry) && (getEntry((Map.Entry<K,V>)o) != null);
    } //contains

    /**
     * Return the Size of the Map Data
     *
     * @return Map Entry Count 
     */
    @Override
    public int size () {
      return SplayTreeMap.this.size();
    } //size

    /**
     * Clear all Entries from the Set and Map
     */
    @Override
    public void clear () {
      SplayTreeMap.this.clear();
    } //clear

    /**
     * Remove the specified Entry from the Set and Map
     *
     * @param o The Map Entry to remove
     * @return true if successfully removed
     */
    @Override
    @SuppressWarnings("unchecked")
    public boolean remove (Object o) {
      if(o instanceof Map.Entry) {
        Entry<K,V> e = getEntry((Map.Entry<K,V>)o);
        if(e != null) {
          SplayTreeMap.this.remove(e.key);
          return true;
        }
      }
      return false;
    } //remove

  } //*EntrySet

} //*SplayTreeMap
